#include <vector>

using namespace std;

class NumMatrix {
private:
    vector<vector<int>> sum;
public:
    NumMatrix(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) {
            return;
        }
        int height = matrix.size();
        int width = matrix[0].size();
        sum.assign(height, vector<int>(width, 0));
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                if (i == 0 && j == 0) {
                    sum[i][j] = matrix[i][j];
                } else if (i == 0) {
                    sum[i][j] = matrix[i][j] + sum[i][j - 1];
                } else if (j == 0) {
                    sum[i][j] = matrix[i][j] + sum[i - 1][j];
                } else {
                    sum[i][j] = matrix[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
                }
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        int ans = sum[row2][col2];
        if (row1 > 0) {
            ans -= sum[row1 - 1][col2];
        }
        if (col1 > 0) {
            ans -= sum[row2][col1 - 1];
        }
        if (row1 > 0 && col1 > 0) {
            ans += sum[row1 - 1][col1 - 1];
        }
        return ans;
    }
};

int main() {
    vector<vector<int>> input = {{3, 0, 1, 4, 2},
    {5, 6, 3, 2, 1},
    {1, 2, 0, 1, 5},
    {4, 1, 0, 1, 7},
    {1, 0, 3, 0, 5}};
    NumMatrix numMatrix(input);
    numMatrix.sumRegion(2, 1, 4, 3);
}
